#include <stdio.h>
#include <stdbool.h>

/*
冒泡排序外循环优化：
若整个序列达到了有序但趟数还没有达到n-1趟时，剩下的趟数就没必要执行了
加一个bool变量来判断整个序列是否有序就行，若达到有效就直接退出循环
*/
void bubble_sort(int *arr, int num)
{	
	//该循环决定趟数
	for(int i = 0; i < num - 1; i++)
	{
		bool flag = true;
		//该循环决定每趟中元素比较的次数
		for(int j = 0; j < num - 1 - i; j++)
		{
			if( arr[j] > arr[j+1])
			{
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
				flag = false;
			}
		}
		printf("第%d轮排序：", i);
		for(int k = 0; k < num; k++)
		{
			printf("%d ", arr[k]);
		}
		printf("\n");
		
		// 判断整个数组是否有序
		if(flag)
		{
			break;
		}
	}
}

int main()
{
   /*  Write C code in this online editor and run it. */
    int i = 0;
	int arr[] = {3,5,9,2,4,7};
	int sz = sizeof(arr) / sizeof(arr[0]);
	
	printf("原始排序：");
	for(i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	bubble_sort(arr, sz);
	printf("最终排序：");
	for(i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
   
   
   return 0;
}